package Midium;

import java.util.Stack;

// 思路二: 思路一在我的电脑上可以跑通，但是在Leetcode上会超时，比如测试一千个"a"组成的字符串，比较的次数太多了！因此要进行优化
// 优化思路：比较最大的串，如果不是回文串再比较子串，比如测试abcbaea，先比较abcbaea，再比较abcba。
// 优化原理：如果大串是回文串，则不考虑其内部的子串
// 写的时候发现这样做还可以避免很多i的边界比较问题，进一步提高了效率
public class Solution5_2 {
    public static String longestPalindrome(String s) {
        if (s.length() == 0)
            return "";
        if (s.length() == 1)
            return s;
        int i = 1, j = 0;
        String sub = s.substring(0, 1);//如果最后没有回文串，那就返回第一个字符，因为第一个字符本身也是回文串
        int maxLen = 0;
        Stack stack = new Stack();
        while (j < s.length()) {
            for (; i < s.length(); i++) {
                if (s.charAt(j) == s.charAt(i))
                    stack.add(i);
            }
            while (!stack.isEmpty()){
                int index = (int)stack.pop();
//                if (hashCalculation(s.substring(j, index + 1)) && s.substring(j, index + 1).length() > maxLen) {
//                    sub = s.substring(j, index + 1);
//                    maxLen = sub.length();
//                    break;
//                }
                if (isPalindrome(s.substring(j, index + 1)) && s.substring(j, index + 1).length() > maxLen) {
                    sub = s.substring(j, index + 1);
                    maxLen = sub.length();
                    break;
                }
            }
            stack.clear();
            j++;
            i=j+1;
            // 如果 maxLen已经比剩余子串的总长度还长，则可以跳出循环
            if(maxLen>s.substring(j,s.length()).length())
                break;
        }

        return sub;
    }
    // 事实证明直接比较会比计算哈希要快
    public static boolean isPalindrome(String s){
        for(int i = 0 , j = s.length()-1 ; i<s.length()/2 ; i++,j--)
            if(s.charAt(i)!=s.charAt(j))
                return false;
        return true;
    }

    public static boolean hashCalculation(String s) {
        long forward = 0, reverse = 0;
        //奇数则算[0,len/2]和[len/2,len)，偶数则算[0,len/2)和[len/2,len)
        int len = s.length();
        int i = 0, j = len - 1;
        int k = 0;
        for (; i < len / 2; i++,k++) {
            forward += Math.pow(26, k) * s.charAt(i);
            if(k%5==0)
                k=0;
        }
        if (len % 2 != 0) {
            //len为奇数奇数
            forward += Math.pow(26, k) * s.charAt(i);
        }
        for (k = 0; j > len / 2 - 1; j--, k++) {
            reverse += Math.pow(26, k) * s.charAt(j);
            if(k%5==0)
                k=0;
        }
        return forward == reverse;
    }

    public static void main(String[] args) {
        System.out.println(longestPalindrome("abcbadeedabcb"));
    }
}
